<html>
<head><meta charset="utf-8"><title>HashMap optiimisations from the type system. · t-libs · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/index.html">t-libs</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/HashMap.20optiimisations.20from.20the.20type.20system.2E.html">HashMap optiimisations from the type system.</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="190496801"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/HashMap%20optiimisations%20from%20the%20type%20system./near/190496801" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Ben <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/HashMap.20optiimisations.20from.20the.20type.20system.2E.html#190496801">(Mar 13 2020 at 12:28)</a>:</h4>
<p>I don't know if this is the right place to ask, or if this will go anywhere: I'm naively thinking, that if you can promise to the type system that all keys fit certain constraints (such as monotonically increasing), and that a hash function can be selected based on said constraints, you are statically encoding information that might allow for some optimisations.</p>
<p>The seed of this idea came from <a href="https://en.wikipedia.org/wiki/Hash_table#Monotonic_keys" target="_blank" title="https://en.wikipedia.org/wiki/Hash_table#Monotonic_keys">this wikipedia</a> chapter on monotonic keys. It's saying that all existing entries do not need to be rehashed and moved, potentially opening the door to more run-time optimizations in terms of memory allocation, entry movement, etc.,. I could see this being of particular interest to hard real-time systems, as open-addressing lookup has to be treated as O(n) and not O(1)~, but with the partitions as described in the link, it can constrain the lookup complexity to <code>O(max(log(log n), max(partition_sizees))</code>.</p>
<p>I've no idea how to go about pulling on this thread in more detail - I'm just a u-grad student. I thought there might be some people here that would at least be help me in where to direct my inquiries.</p>



<a name="190497622"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/HashMap%20optiimisations%20from%20the%20type%20system./near/190497622" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/HashMap.20optiimisations.20from.20the.20type.20system.2E.html#190497622">(Mar 13 2020 at 12:38)</a>:</h4>
<p>If you know some particular quantities of your data set, it may indeed be beneficial to swap out your hash function (which is mostly a matter of providing a struct to the HashMap implementing hasher). But this isn't really something that is going to happen automatically (ever) I'm guessing.</p>



<a name="190497746"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/HashMap%20optiimisations%20from%20the%20type%20system./near/190497746" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/HashMap.20optiimisations.20from.20the.20type.20system.2E.html#190497746">(Mar 13 2020 at 12:40)</a>:</h4>
<p>And for very particular cases -- e.g. monotonic keys -- it may even be the case that a hashmap is not what you want, but instead just a Vec + push and search via binary_search. But it really depends on your exact use case.</p>



<a name="190498425"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/HashMap%20optiimisations%20from%20the%20type%20system./near/190498425" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Ben <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/HashMap.20optiimisations.20from.20the.20type.20system.2E.html#190498425">(Mar 13 2020 at 12:49)</a>:</h4>
<p>For me, I'm doing an indexed binary heap implemented priority queue. Going to serve as a data structure for my hobby OS projects timer driver. Need O(log n) queue deletion by entry ID. Id's have to be unique per entry.</p>



<a name="190498572"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/HashMap%20optiimisations%20from%20the%20type%20system./near/190498572" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/HashMap.20optiimisations.20from.20the.20type.20system.2E.html#190498572">(Mar 13 2020 at 12:50)</a>:</h4>
<p>I would ask on <a href="http://users.rust-lang.org" target="_blank" title="http://users.rust-lang.org">users.rust-lang.org</a> (or perhaps #general), Zulip and such are mostly intended for team work rather than sort of general questions</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>